package bintree.leetcode;

/**
 * @Author: yuisama
 * @Date: 2022/9/28 18:24
 * @Description:构造最大二叉树
 */
public class Num654_ConstructMaximumBinaryTree {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return constructMaximumBinaryTreeInternal(nums,0,nums.length - 1);
    }

    /**
     * 在数组nums[left..right]上构建最大二叉树，返回二叉树的树根
     * @param nums
     * @param left
     * @param right
     * @return
     */
    private TreeNode constructMaximumBinaryTreeInternal(int[] nums, int left, int right) {
        // base case
        if (left > right) {
            return null;
        }
        // 前序位置，先找到当前数组上最大值构建根节点
        int max = findMax(nums,left,right);
        TreeNode root = new TreeNode(nums[max]);
        root.left = constructMaximumBinaryTreeInternal(nums,left,max - 1);
        root.right = constructMaximumBinaryTreeInternal(nums,max + 1,right);
        return root;
    }

    /**
     * 在数组nums[left..right]上寻找最大值,返回最大值下标
     * @param nums
     * @param left
     * @param right
     * @return
     */
    private int findMax(int[] nums, int left, int right) {
        int maxIndex = left;
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}
